package binaryTree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
 *@description 二叉搜索树迭代器
 *@author hkfan
 *@version 1.0
 *@create 2025/6/16 15:36
 */
public class LeetCode_173 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * @description 方法1：使用数组存储，但是空间复杂度O（n），需要优化
     * @author hkfan
     * @time 2025/6/18 09:45
     */
    class BSTIterator1 {

        List<TreeNode> list;
        int i;

        public BSTIterator1(TreeNode root) {
            list = new ArrayList<>();
            recordData(list,root);
            i=0;
        }

        private void recordData(List<TreeNode> list, TreeNode root) {
            if (root!=null){
                recordData(list,root.left);
                list.add(root);
                recordData(list,root.right);
            }
        }

        public int next() {
            return list.get(i++).val;
        }

        public boolean hasNext() {
            return i<list.size();
        }
    }

    /**
     * @description 方法2：使用栈实现，空间复杂度O（h），h为树高（中序遍历的非递归实现）
     * @author hkfan
     * @time 2025/6/18 09:45
     */
    class BSTIterator2 {

        Stack<TreeNode> stack;

        public BSTIterator2(TreeNode root) {
            stack=new Stack<>();
            while (root!=null){
                stack.add(root);
                root=root.left;
            }
        }



        public int next() {
            TreeNode node = stack.pop();
            if (node.right!=null){
                TreeNode temp = node.right;
                while (temp!=null){
                    stack.add(temp);
                    temp=temp.left;
                }
            }
            return node.val;
        }

        public boolean hasNext() {
            return !stack.isEmpty();
        }
    }
}
